package java学习.leetcode.editor.cn;
/**
 * @author 刘世锦
 * 2023-01-04 12:37:23	 当前时间
 */
//给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的
//根节点的引用。 
//
// 一般来说，删除节点可分为两个步骤： 
//
// 
// 首先找到需要删除的节点； 
// 如果找到了，删除它。 
// 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入：root = [5,3,6,2,4,null,7], key = 3
//输出：[5,4,6,2,null,null,7]
//解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
//一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
//另一个正确答案是 [5,2,6,null,4,null,7]。
//
//
// 
//
// 示例 2: 
//
// 
//输入: root = [5,3,6,2,4,null,7], key = 0
//输出: [5,3,6,2,4,null,7]
//解释: 二叉树不包含值为 0 的节点
// 
//
// 示例 3: 
//
// 
//输入: root = [], key = 0
//输出: [] 
//
// 
//
// 提示: 
//
// 
// 节点数的范围 [0, 104]. 
// -105 <= Node.val <= 105 
// 节点值唯一 
// root 是合法的二叉搜索树 
// -105 <= key <= 105 
// 
//
// 
//
// 进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。 
// Related Topics 树 二叉搜索树 二叉树 
// 👍 1035 👎 0

public class 删除二叉搜索树中的节点{
	public static void main(String[] args) {
		Solution solution = new 删除二叉搜索树中的节点().new Solution();
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

	/** 复习  @author 刘世锦
	 *  @date  2023/2/13 21:44
	 */
	public TreeNode deleteNode(TreeNode root, int key) {

		if (root==null){
			return root;
		}
		if (root.val>key){
			root.left = deleteNode(root.left,key);
		}else if (root.val<key){
			root.right = deleteNode(root.right,key);
		}else{
			if (root.right!=null){
				TreeNode cur = root.right;
				TreeNode node = cur;
				TreeNode left = root.left;
				while (cur.left!=null){
					cur = cur.left;
				}
				cur.left = left;
				return node;
			}else if (root.left!=null){
				return root.left;
			}else{
				return null;
			}
		}
			return root;
	}
	// 复习end



	/**
	 * 请意识到： 递归返回的是删除完节点后的子树。
	 * 	进而巧妙的不用考虑父节点怎么与 子节点连接
	 * 	因为返回的就是子节点。
	 *
	 */
	public TreeNode deleteNode2(TreeNode root, int key) {
		if (root==null){
			return root;
		}
		if (root.val == key){
			/**
			 * 此时 node 为 需要删除的节点
			 * 1. node 的left、right都不为空
			 * 		将left左子树 变成 right右子树最左下角的左孩子
			 * 2. node left != null
			 * 		父节点连接 node.left。 即：返回node左孩子
			 * 3. node right != null
			 * 		父节点连接 node.right。 即：返回node右孩子
			 * 4. node为叶子节点
			 * 		父节点连接 null。 即 返回null
			 */
			if (root.left!=null&&root.right!=null){
				TreeNode right = root.right;
				TreeNode cur = right;
				TreeNode left = root.left;
				while (right.left!=null){
					right = right.left;
				}
				right.left = left;
				return cur;
			}else if (root.left!=null){
				return root.left;
			}else if (root.right!=null){
				return root.right;
			}else{
				return null;
			}
		}

		if (root.val>key){
			root.left = deleteNode(root.left,key);
		}else{
			root.right = deleteNode(root.right,key);
		}
		return root;


	}

	public TreeNode deleteNodeDFS(TreeNode root, int key) {
		if (root==null){
			return root;
		}
		if (root.val == key){
			if (root.right==null){
				root = root.left;
			}else{
				TreeNode right = root.right;
				TreeNode left = root.left;
				root = root.right;
				TreeNode cur = root;
				while (cur.left!=null){
					cur = cur.left;
				}
				cur.left = left;
			}
		}
		TreeNode node = root;
		TreeNode pre = null;
		while (node!=null){
			if (node.val>key){
				pre = node;
				node = node.left;
			}else if (node.val<key){
				pre = node;
				node = node.right;
			}else{
				if (node.right!=null&&node.left!=null){
					if (pre!=null) {
						TreeNode left = node.left;
						TreeNode right = node.right;

						TreeNode cur = right;
						while (cur.left != null) {
							cur = cur.left;
						}
						cur.left = left;
						if (pre.val>node.val){
							pre.left = cur;
							break;
						}else{
							pre.right = cur;
							break;
						}
					}
				}else if (node.right!=null){
					if (pre!=null){
						if (pre.val>node.val){
							pre.left = node.right;
							break;
						}else{
							pre.right = node.right;
							break;
						}
					}
				}else if (node.left!=null){
					if (pre!=null){
						if (pre.val>node.val){
							pre.left = node.left;
							break;
						}else{
							pre.right = node.left;
							break;
						}
					}
				} else{
					if (pre.val>node.val){
						pre.left = null;
						break;
					}else{
						pre.right = null;
						break;
					}
				}
			}
		}
		return root;
    }
}
/**
 *      5               4              4               3              5
 *    /  \               \              \             / \           /  \
 *   3    7              7              8            2  5          3    6
 *  / \  / \            / \            / \             / \        / \  / \
 * 1  4 6   8          6  8           6  9            4  10      2  4     7
 *                    /    \         /    \             / \
 *                   5     9        5     9            8  15
 *                                                    /
 *                                                   7
 */
//leetcode submit region end(Prohibit modification and deletion)

}
